Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 23 Issue 4
July  2008
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Lu-An Tang, Bin Cui, Hong-Yan Li, Gao-Shan Miao, Dong-Qing Yang, Xin-Biao Zhou. PGG: An Online Pattern Based Approach for Stream Variation Management[J]. Journal of Computer Science and Technology, 2008, 23(4): 497-515.
Citation: Lu-An Tang, Bin Cui, Hong-Yan Li, Gao-Shan Miao, Dong-Qing Yang, Xin-Biao Zhou. PGG: An Online Pattern Based Approach for Stream Variation Management[J]. Journal of Computer Science and Technology, 2008, 23(4): 497-515.
shu

PGG: An Online Pattern Based Approach for Stream Variation Management

  • {\it 1Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, 61801, U.S.A.2School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China3Key Laboratory of Machine Perception (Ministry of Education), Peking University, Beijing 100871, China4Key Laboratory of High Confidence Software Technologies (Ministry of Education), Peking University, Beijing 100871, China

More Information
  • Received Date: April 13, 2008
  • Revised Date: June 02, 2008
  • Published Date: July 09, 2008
    Abstract
  • Many database applications require efficient processing ofdata streams with value variations and fluctuant sampling frequency.The variations typically imply fundamental features of the stream andimportant domain knowledge of underlying objects. In some datastreams, successive events seem to recur in a certain time interval,but the data indeed evolves with tiny differences as time elapses. Thisfeature, so called {\it pseudo periodicity}, poses a new challenge tostream variation management. This study focuses on the onlinemanagement for variations over such streams. The idea can be applied tomany scenarios such as patient vital signal monitoring in medicalapplications. This paper proposes a new method named Pattern GrowthGraph (PGG) to detect and manage variations over evolving streams withfollowing features: 1) adopts the wave-pattern to capture the majorinformation of data evolution and represent them compactly; 2) detectsthe variations in a single pass over the stream with the help ofwave-pattern matching algorithm; 3) only stores different segments ofthe pattern for incoming stream, and hence substantially compresses thedata without losing important information; 4) distinguishes meaningfuldata changes from noise and reconstructs the stream with acceptableaccuracy. Extensive experiments on real datasets containing millions ofdata items, as well as a prototype system, are carried out todemonstrate the feasibility and effectiveness of the proposed scheme.
    • FullText(HTML)
    • References (45)
  • [1] Papadimitriou S, Yu P S. Optimal multi-scale patterns in time series streams. In {\it Proc. the 2006 ACM SIGMOD International Conference on Management of Data}, Chicago, IL, USA, June 27--29, 2006, pp.647--658.
    [2]
    } Aggarwal C C, Han J, Wang J, Yu P S. A framework for projected clustering of high dimensional data streams. In {\it Proc. the Thirtieth International Conference on Very Large Data Bases}, Toronto, Canada, August 31--September 3, 2004, Vol.30, pp.852--863.
    [3]
    } Wang H, Fan W, Yu P S, Han J. Mining concept-drifting data streams using ensemble classifiers. In {\it Proc. the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining}, KDD'03, Washington D C, August 24--27, 2003, pp.226--235.
    [4]
    } Babcock B, Datar M, Motwani R, O'Callaghan L. Maintaining variance and k-medians over data stream windows. In {\it Proc. the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'03}, San Diego, California, June 9--11, 2003, pp.234--243.
    [5]
    } Wang H, Pei J, Yu P S. Online mining data streams: Problems, applications and progress. In {\it Proc. the 21st International Conference on Data Engineering, ICDE'05}, Tokyo, Japan, April 5--8, 2005.
    [6]
    } Keogh E, Lin J, Fu A. HOT SAX: Efficiently finding the most unusual time series subsequence. In {\it Proc. Fifth IEEE International Conference on Data Mining}, Houston, Texas, USA, Nov. 2005, pp.27--30.
    [7]
    } Keogh E, Lonardi S, Chiu B. Finding surprising patterns in a time series database in linear time and space. In {\it Proc. the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining}, Edmonton, Alberta, Canada, July 23--26, 2002, pp.550--556.
    [8]
    } Wu H, Salzberg B, Zhang D. Online event-driven subsequence matching over financial data streams. In {\it Proc. the 2004 ACM SIGMOD International Conference on Management of Data}, Paris, France, June 13--18, 2004, pp.23--34.
    [9]
    } Varon Joseph, Marik PE. Clinical information systems and the electronic medical record in the intensive care unit. {\it Current Option in Critical Care}, 2002, 8(6): 616--624.
    [10]
    } Zhou X, Miao G, Li H, Tang L, Wei X. PEDS-VM: A variation management prototype for pattern evolving data streams. In {\it Proc. the Ninth International Conference on Web-Age Information Management, WAIM 08}, Zhangjiajie, China, July 20--22, 2008. (To appear)
    [11]
    } Tang L, Cui B, Li H, Miao G, Yang D, Zhou X. Effective variation management for pseudo periodical streams. In {\it Proc. the 2007 ACM SIGMOD International Conference on Management of Data}, %SIGMOD'07, Beijing, China, June 11--14, 2007, pp.257--268.
    [12]
    } Papadimitriou S, Sun J, Faloutsos C. Streaming pattern discovery in multiple time-series. In {\it Proc. the 31st International Conference on Very Large Data Bases}, Trondheim, Norway, August 30 -- September 02, 2005, pp.697--708.
    [13]
    } Babu S, Widom J. Continuous queries over data streams. {\it SIGMOD Rec.}, Sept. 2001, 30(3): 109--120.
    [14]
    } Abadi D, Carney D, Cetintemel U, Cherniack M, Convey C, Lee S, Stonebraker M, Tatbul N, Zdonik S. Aurora: A new model and architecture for data stream management. {\it The VLDB Journal}, August 2003, 12(2): 120--139.
    [15]
    } Cortes C, Fisher K, Pregibon D, Rogers A. Hancock: A language for extracting signatures from data streams. In {\it Proc. the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining}, Boston, Massachusetts, United States, August 20--23, 2000, pp.9--17.
    [16]
    } Chandrasekaran S, Cooper O, Deshpande A, Franklin M J, Hellerstein J M, Hong W, Krishnamurthy S, Madden S R, Reiss F, Shah M A. TelegraphCQ: Continuous dataflow processing. In {\it Proc. the 2003 ACM SIGMOD International Conference on Management of Data}, %SIGMOD'03, San Diego, California, June 9--12, 2003, pp.668--668.
    [17]
    } Sullivan M. Tribeca: A stream database manager for network traffic analysis. In {\it Proc. the 22nd International Conference on Very Large Data Bases}, San Francisco, CA, September 3--6, 1996, p.594.
    [18]
    } Yao Y, Gehrke J. The cougar approach to in-network query processing in sensor networks. {\it SIGMOD Rec.}, Sept. 2002, 31(3): 9--18.
    [19]
    } Cormode G, Datar M, Indyk P, Muthukrishnan S. Comparing data streams using Hamming norms (how to zero in). In {\it Proc. the 28th International Conference on Very Large Data Bases}, Hong Kong, China, August 20--23, 2002, pp.335--345.
    [20]
    } Datar M, Gionis A, Indyk P, Motwani R. Maintaining stream statistics over sliding windows. In {\it Proc. the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms}, San Francisco, California, January 6--8, 2002, pp.635--644.
    [21]
    } Hu Z, Li H, Qiu B, Tang L, Fan Y, Liu H, Gao J, Zhou X. Using control theory to guide load shedding in medical data stream management system. In {\it Proc. the 10th Asian Computing Science Conference, Advances in Computer Science, 2005}, Kunming, China, {\it LNCS} 3818, pp.236--248.
    [22]
    } Ganguly S, Garofalakis M, Rastogi R. Processing set expressions over continuous update streams. In {\it Proc. the 2003 ACM SIGMOD International Conference on Management of Data}, %SIGMOD'03, San Diego, California, June 9--12, 2003, pp.265--276.
    [23]
    } David J Fraenkel, Melleesa Cowie, Peter Daley. Quality benefits of an intensive care clinical information system. {\it Crit. Care Medi.}, 2003, 31: 120--125.
    [24]
    } Axel Junger, Achim Michel {\it et al}. Evaluation of the suitability of a patient data management system for ICUs on a general ward. {\it International Journal of Medical Informatics}, 2001, 64: 57--66.
    [25]
    } Liu Y B, Cai J R, Yin J, Fu W A. Clustering text data streams. {\it Journal of Computer Science and Technology}, Jan. 2008, 23(1): 112--128.
    [26]
    } Hu X G, Li P P, Wu X D, Wu G Q. A semi-random multiple decision-tree algorithm for mining data streams. {\it Journal of Computer Science and Technology}, Sept. 2007, 22(5): 711--724.
    [27]
    } Chong Z H, Yu J X, Zhang Z J, Lin X M, Wang W, Zhou A Y. Efficient computation of k-medians over data streams under memory constraints. {\it Journal of Computer Science and Technology}, Mar. 2006, 21(2): 284--296.
    [28]
    } Chang J H, Lee W S. Effect of count estimation in finding frequent itemsets over online transactional data streams. {\it Journal of Computer Science and Technology}, Jan. 2005, 20(1): 63--69.
    [29]
    } Cai Y D, Clutter D, Pape G, Han J, Welge M, Auvil L. MAIDS: Mining alarming incidents from data streams. In {\it Proc. the 2004 ACM SIGMOD International Conference on Management of Data}, Paris, France, June 13--18, 2004, %SIGMOD'04. pp.919--920.
    [30]
    } Teng W, Chen M, Yu P S. A regression-based temporal pattern mining scheme for data streams. In {\it Proc. the 29th International Conference on Very Large Data Bases}, Berlin, Germany, September 09--12, 2003, pp.93--104.
    [31]
    } Zhu Y, Shasha D. Efficient elastic burst detection in data streams. In {\it Proc. the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining}, Washington D C, August 24--27, 2003, pp.336--345.
    [32]
    } Ma J, Perkins S. Online novelty detection on temporal sequences. In {\it Proc. the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining}, Washington D C, August 24--27, 2003, pp.613--618.
    [33]
    } Aggarwal C C. On abnormality detection in spuriously populated data streams. In {\it Proc. SIAM International Conference on Data Mining}, Newport Beach, CA, USA, 2005.
    [34]
    } Lin J, Keogh E, Lonardi S, Chiu B. A symbolic representation of time series, with implications for streaming algorithms. In {\it Proc. the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery}, San Diego, California, June 13, 2003, pp.2--11.
    [35]
    } Gilbert A C, Kotidis Y, Muthukrishnan S {\it et al}. One-Pass Wavelet Decompositions of Data Streams. {\it IEEE Trans. Knowl. and Data Eng.}, Mar. 2003, 15(3): 541--554.
    [36]
    } Papadimitriou S, Brockwell A, Faloutsos C. Adaptive, unsupervised stream mining. {\it The VLDB Journal}, Sept. 2004, 13(3): 222--239.
    [37]
    } Gao L, Wang X. Continuous similarity-based queries on streaming time series. {\it IEEE Trans. Knowl. Data Eng.}, Oct. 2005, 17(10): 1320--1332.
    [38]
    } Wu H, Salzberg B, Zhang D. Online event-driven subsequence matching over financial data streams. In {\it Proc. the 2004 ACM SIGMOD International Conference on Management of Data}, Paris, France, June 13--18, 2004, pp.23--34.
    [39]
    } Wu H, Sharp G, Salzberg B, Kaeli D, Shirato H, Jiang S. A finite state model for respiratory motion analysis in image guided radiation therapy. {\it Physics in Medicine and Biology (PMB)}, 2004, 49(23): 5357--5372.
    [40]
    } Wu H, Salzberg B, Sharp G C, Jiang S B, Shirato H, Kaeli D. Subsequence matching on structured time series data. In {\it Proc. the 2005 ACM SIGMOD International Conference on Management of Data}, Baltimore, Maryland, June 14--16, 2005, pp.682--693.
    [41]
    } Aggarwal C C. A framework for diagnosing changes in evolving data streams. In {\it Proc. the 2003 ACM SIGMOD International Conference on Management of Data}, San Diego, California, June 09--12, 2003, pp.575--586.
    [42]
    } Wang H, Pei J. A random method for quantifying changing distributions in data streams. In {\it Proc. the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD)}, Porto, Portugal, October 2005, pp.684--691.
    [43]
    } Keogh E J, Chu S, Hart D, Pazzani M J. An online algorithm for segmenting time series. In {\it Proc. the 2001 IEEE International Conference on Data Mining}, Cercone N (ed), November 29--December 02, 2001, pp.289--296.
    [44]
    } http://peer.berkeley.edu/nga/flatfile.html
    [45]
    } http://www.schoolsobservatory.org
    • Relative Articles

  • Related Articles

    [1]WANG wen jun, ZHONG Cuihao. The Distributed Workflow Management System - Flow Agent[J]. Journal of Computer Science and Technology, 2000, 15(4): 376-382.
    [2]LUO Junzhou, GU Guanqun, FEI Xiang. An Architectural Model for Intelligent Network Management[J]. Journal of Computer Science and Technology, 2000, 15(2): 136-143.
    [3]WANG Jian, ZHANG Fuyan. Multicast Address Management and Connection Control Based on Hierarchical Autonomous Structure[J]. Journal of Computer Science and Technology, 1999, 14(1): 64-73.
    [4]Gu Ning, Lin Zongkai, Guo Yuchai. On Model, Memory Management and Interface in EDBMS/3[J]. Journal of Computer Science and Technology, 1998, 13(4): 337-347.
    [5]Zhou Longxiang, Qin Jiying. The Catalog Management Strategy of Distributed Data Base Systems[J]. Journal of Computer Science and Technology, 1994, 9(3): 193-203.
    [6]Pong Man-Chi, Zhang Yongguang, Xu Hong, Ding Jie. OOMMS:A Module Management System Based on an Object-Oriented Model[J]. Journal of Computer Science and Technology, 1993, 8(2): 76-85.
    [7]Zhang Chenxi, Ci Yungui. Management of Statically Modifiable Prolog Code[J]. Journal of Computer Science and Technology, 1989, 4(4): 323-333.
    [8]Zhang Fuyan, Cai Shijie, Wang Shu, Ge Ruding. The Human-Computer Dialogue Management of FCAD System[J]. Journal of Computer Science and Technology, 1988, 3(3): 221-227.
    [9]Tai Juwei, Wang Jue, Chen Xin. A Syntactic-Semantic Approach for Pattern Recognition and Knowledge Representation[J]. Journal of Computer Science and Technology, 1988, 3(3): 161-172.
    [10]Wang Hanhu. Transaction Management in Distributed Database System POREL[J]. Journal of Computer Science and Technology, 1988, 3(2): 139-146.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (18) PDF downloads (1210) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return